|
In graph theory, a graceful labeling of a graph with ''m'' edges is a labeling of its vertices with some subset of the integers between 0 and ''m'' inclusive, such that no two vertices share a label, and such that each edge is uniquely identified by the positive, or absolute difference between its endpoints.〔Virginia Vassilevska, "Coding and Graceful Labeling of trees." SURF 2001. (PostScript )〕 A graph which admits a graceful labeling is called a graceful graph. The name "graceful labeling" is due to Solomon W. Golomb; this class of labelings was originally given the name β-labelings by Alexander Rosa in a 1967 paper on graph labelings.〔.〕 A major unproven conjecture in graph theory is the Graceful Tree conjecture or Ringel–Kotzig conjecture, named after Gerhard Ringel and Anton Kotzig, which hypothesizes that all trees are graceful. The Ringel-Kotzig conjecture is also known as the "graceful labeling conjecture". Kotzig once called the effort to prove the conjecture a "disease".〔.〕 ==Selected results== *In his original paper, Rosa proved that an Eulerian graph with number of edges ''m'' ≡ 1 (mod 4) or ''m'' ≡ 2 (mod 4) can't be graceful.〔 *Also in his original paper, Rosa proved that the cycle ''Cn'' is graceful if and only if ''n'' ≡ 0 (mod 4) or ''n'' ≡ 3 (mod 4). *All path graphs and caterpillar graphs are graceful. *All lobster graphs with a perfect matching are graceful.〔.〕 *All trees with at most 27 vertices are graceful; this result was shown by Aldred and McKay in 1998 using a computer program.〔.〕〔.〕 An extension of this (using a different computational method) up to trees with 35 vertices was claimed in 2010 by the Graceful Tree Verification Project, a distributed computing project led by Wenjie Fang.〔. See also (Graceful Tree Verification Project )〕 *All wheel graphs, web graphs, Helm graphs, gear graphs, and rectangular grids are graceful.〔 *All ''n''-dimensional hypercubes are graceful.〔.〕 *All simple graphs with four or fewer vertices are graceful. The only non-graceful simple graphs with five vertices are the 5-cycle (pentagon); the complete graph ''K''5; and the butterfly graph. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Graceful labeling」の詳細全文を読む スポンサード リンク
|